There are two major areas of the art of networking security, encryption and authentication. Encryption is a method of hiding or encrypting the data in transmission so that only the recipient may have access to the data in its unhidden or unencrypted form. This is also known as data privacy. Authentication on the other hand is a method of ensuring that a transmission that is sent from a sender to a receiver in fact came from the true sender. This is otherwise known as integrity. A method that provides encryption ensures that only the appropriate and intended receiver may possess the method to decrypt the data for use, and a method that provides authentication ensures that only an appropriate and valid sender of a transmission did indeed sign the message with a uniquely identifiable and verifiable signing method.
The area of security that the present invention is concerned with is authentication. There are two major groupings of authentication methods in use today, public key and private key methods. In private key authentication, the method employs a secret, shared key which is known only to the sender and the receiver. In providing key authentication, a data transmission is uniquely manipulated by use of an algorithm using the private key before being sent to the receiver. A receiver, receiving such a manipulated transmission, uses a reciprocal algorithm to the sender's algorithm and the sender's private key to uniquely read the message. Since only the sender and the receiver know the secret key, only the sender could have manipulated the message so that the receiver could read it.
The problem with private key authentication is the transfer of the sender's secret or private key to the receiver. In addition, secret keys in private key authentication are often breakable given the amount of computing power available today, and are difficult to maintain. In addition, the lifespan of the key is relatively short due to the inherent breakability and difficulty in securely transmitting the private key over an unsecure network. Typically, private key authentication is used when there is an out of band channel available to send private keys outside of the unsecure network, such as a military installation with a dedicated, secret radio key transmitter. Also, transmissions using private key authentication are often small due to the necessary processing overhead for each packet of the transmission; the larger the packet, the larger the overhead needed to run the secret algorithms on the data.
Public key authentication eliminates the secure key transfer problem inherent with private key authentication. In public key authentication, a pair of reciprocal keys is used between the sender and receiver, the sender's private and public keys. The unique property of public key authentication is that a message received and verified with an algorithm using the sender's public key could only have been signed using the sender's particular and reciprocal private key of that pair.
Public key methods make use of the property that extremely large numbers, the numbers used to manipulate the transmitted messages, are extremely expensive to factor into smaller numbers while the smaller numbers, which are the keys themselves, are very easy to multiply together to get the large cipher number. In each pair of keys used by the sender and the receiver, each of the entities holds one and only one of the keys as well as the multiplied large number. From this, it is easy to determine the content of the message through a mathematical algorithm which does not reveal the reciprocal key.
Because of these properties, many schemes, such as the widely used SSL and HTTPS, employ public key schemes. However, the expensive processing cost used in the algorithm needed to take the extremely large cipher number and manipulate the data with it make it very difficult for typical servers receiving appreciable traffic to use because of the high per transaction authentication costs. Unlike private key cryptography, there is no benefit for very small transactions as small data sizes still take a significant initial processing investment to get started. Therefore, the public key schemes are suited for large transmissions with fewer transactions, but unsuitable for the high frequency, smaller transactions typically found on the Internet.
With both public and private key cryptography, processing is done on a per-transmission basis, resulting in bloated processing on the entity which is performing the authentication. With the processing power available to malicious individuals spying on network traffic, it is also impractical to vary the keys of the private key method at a high enough frequency because of the difficulty of sending the shared keys securely over an unsecure network. The only way to reduce the processing overhead is to reduce the authentication strength, to decrease the frequency of key refreshes in private key methods, and to reduce the size and strengths of the keys in public key authentication. This, of course, is unacceptable for sensitive information such as credit card information, stock trading activity, and voting which frequently needs to be sent through unsecure networks.
Thus, there exists a need for efficiently authenticating data from a user transmitting over an unsecure network that requires both low processing overhead, yet still prevents a third-party from impersonating the data from a legitimate user.